1. Field of the Invention
The present invention generally relates to processor architectures and data routing structures. More particularly, the present invention is a system and method for implementing data processing using a Banyan switch.
2. Description of the Related Art
In general, two types of tasks may be performed in a computing environment (i.e., data transformation and data transfer). Data transformation encompasses the manners in which the content of data signals may be selectively altered, such as via mathematical or logical operations. Data transformation is often viewed as the “useful work” performed by a computing system.
Data transfer encompasses the manners in which data signals are moved from a source to a destination. Data transfer is facilitated via an interconnect structure or network, which comprises a particular architectural organization of couplings capable of exchanging data signals between a set of nodes. The nodes may include one or more data sources and one or more data destinations, and the nodes may comprise one or more of processing units, memories, and input/output (I/O) devices.
Interconnect networks generally fall into two categories, static and dynamic. A static interconnect network is characterized by fixed internode couplings, and the couplings between any pair of nodes comprise an unchanging set of mappings. The static interconnect network may have the form of rings, trees, arrays and meshes, tori, hypercubes, k-ary n-cubes, and/or variants thereof FIG. 1 illustrates an exemplary prior art interconnect mesh having couplings that facilitate information exchange between a node 100 and its four nearest-neighbor nodes 110.
In a dynamic interconnect network, a collection of switching elements facilitate selectable coupling between sets of nodes (i.e., data sources and destinations). In other words, the switching elements control the pathways by which information may be exchanged between various nodes. The simplest dynamic interconnect network may be a bus, which can selectably handle one data transfer transaction at a time between a set of data sources and a set of data destinations. Other types of dynamic interconnect networks include multistage switched networks such as crossbar, Omega, Butterfly, and Banyan networks. Multistage dynamic interconnect networks are much more versatile and fault-tolerant than buses.
FIG. 2 is a block diagram of an exemplary 4×4 Banyan network or switch 200. In general, an N×N Banyan switch may comprise log2N or log4N stages of switching elements, and each stage includes N inputs and N outputs. In the case of log2N stages, the Banyan switch 200 comprises two stages 210 and 212, labeled as stage 0 and stage 1, each of which has four inputs and four outputs. The inputs to stage 0 and the outputs of stage 1 respectively form the inputs and outputs of the Banyan switch 200. The outputs of stage 0 are coupled to the inputs of stage 1. One half of the couplings are straight across from stage-to-stage, and the other half forms a crossover pattern from stage-to-stage as shown in FIG. 2.
Each switching stage 210 and 212 comprises a set of switching cells 220. Switching cells 220 may be conventional crossbar switches, capable of transferring signals from any switching cell input to any switching cell output. In the event that an N×N Banyan switch is implemented using 2×2 (i.e., two inputs and two outputs) switching cells 220, each switching stage 210 and 212 comprises N/2 switching cells 220. Each switching cell 220 has a control input 222 for selecting a given switching cell input routed to a given switching cell output. In conjunction with the couplings between switching stages, the set of control inputs 222 determines how data signals present at the inputs of the Banyan switch are routed to the Banyan switch outputs.
Larger, more complex Banyan switches have a greater number of inputs and outputs and support a larger number of input-to-output routing possibilities. For example, FIG. 3 is a block diagram of an exemplary 8×8 Banyan switch 300. The switch 300 has eight inputs and eight outputs, and comprises three switching stages 310, 312 and 314. Each switching stage contains four 2×2 switching cells 320, and each switching cell has a switching cell control input that is not shown in FIG. 3 but is similar to the control inputs 222 in FIG. 2.
In general, the input-to-output mappings inherently provided by the internal architecture of an interconnect network implement particular types of data routing functions or operations. These data routing functions may include shifting, rotation, permutation, exchange, or other functions. For example, the internal couplings within a Banyan switch inherently support 2K-1 shifting and permutations. The execution of such inherent routing functions does not carry a time penalty relative to direct pass-through routing.
Functions such as shifting, rotation, and permutation may also be important within the context of data transformation, either by themselves or as part of a sequence of computational operations. For example, floating point computations may require normalization operations, which can be carried out via shifting. Even though interconnect networks can perform these routing operations with high efficiency, modern processor architectures fail to perform these operations efficiently because the architectures typically implement these functions through successive single-bit shifts.
Hence what is needed is a processor datapath that efficiently supports computationally-advantageous data routing operations.